def merge_sort(arr):
  if len(arr) <= 1:
    return arr
  mid = len(arr) // 2
  left = merge_sort(arr[:mid])
  right = merge_sort(arr[mid:])
  return merge(left, right)


def merge(left, right):
  res = []
  i, j = 0, 0
  while i < len(left) and j < len(right):
    if left[i] <= right[j]:
      res.append(left[i])
      i = i + 1
    elif right[j] < left[i]:
      res.append(right[j])
      j = j + 1
  while i < len(left):
    res.append(left[i])
    i = i + 1
  while j < len(right):
    res.append(right[j])
    j = j + 1
  return res


if __name__ == '__main__':
  res = merge_sort([1, 7, 6, 5, 4, 3, 1])
  print(res)
